package Q647;

/**
 * 回文子串
 *
 * @author 23737
 * @time 2021.12.6
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().countSubstrings("abc"));
        System.out.println(new Solution().check("absa"));
    }
}

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (n == 1) break;
            for (int j = i+1; j < s.length(); j++) {
                String str = s.substring(i, j);
                if (check(str)) {
                    count++;
                }
            }
        }
        return count;
    }

    public boolean check(String s) {
        StringBuilder sb = new StringBuilder();
        String s1 = sb.append(s).reverse().toString();
        return s.equals(s1);
    }
}

class Solution2 {
    public int countSubstrings(String s) {
        // 动态规划法
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans = 0;

        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }

        return ans;
    }
}

